package com.gitee.feizns.explore.data_structure.linked_list.singly.isPalindrome;

import com.gitee.feizns.explore.data_structure.linked_list.singly.ListNode;

/**
 * @author feizns
 * @since 2020/3/4
 */
public class IsPalindrome2 {

    public static void main(String[] args) {
        System.out.println(isPalindrome(create()));
    }

    private static ListNode create() {
        ListNode ret = new ListNode(1);
        ret.next = new ListNode(2);
//        ret.next.next = new ListNode(2);
//        ret.next.next.next = new ListNode(1);
        return ret;
    }

    static ListNode HEAD = null;

    static ListNode MID = null;

    public static boolean isPalindrome(ListNode head) {
        if ( head == null || head.next == null )
            return true;
        HEAD = head;
        ListNode n = new ListNode(-1);
        n.next = head;
        MID = n;
        return equals(head, 1);
    }

    private static boolean equals(ListNode n, int i) {
        if ( n != null ) {
            if ( i % 2 == 0 )
                MID = MID.next;
            if ( n != MID ) {
                if ( equals(n.next, i + 1) ) {
                    if ( n.val != HEAD.val )
                        return false;
                    else
                        HEAD = HEAD.next;
                    return true;
                }
                return false;
            }
        }
        return true;
    }

}
